package top.firejames.sort;


/**
 * @auther 夏浩
 * @creat 2021-09-2021/9/23-15:40
 */
public class MergeSort {
    public static void main(String[] args) {
        int a[] = new int[]{1, 9, 13, 24, 56, 3, 17, 34, 46, 59};
        mergeSort(a, 0, a.length - 1);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");

        }
    }

    //将两个有序的序列归并
    public static void merge1(int[] a, int start, int mid, int end) {
        //辅助空间
        int[] ints = new int[a.length];
        //p，q为两个序列的开始索引
        int p = start, q = mid + 1;
        int k = start;
        //从小到大依次比较两个序列的大小，把小的数放进辅助空间里，直到有一个序列全部放完
        while (p <= mid && q <= end) {
            if (a[p] > a[q]) {
                ints[k++] = a[q++];
            } else {
                ints[k++] = a[p++];
            }
        }
        //剩余一个序列依次次放入辅助空间
        while (p <= mid) {
            ints[k++] = a[p++];
        }
        while (q <= end) {
            ints[k++] = a[q++];
        }
        //把排好序的数组复制到a数组里面
        for (int i = start; i <=end; i++) {
            a[i] = ints[i];
        }
    }

    //采用递归的方法进行归并排序
    public static void mergeSort(int a[], int start, int end) {
        if (start < end) {
            //每次切分的中点
            int mid = (start + end) / 2;
            //每次切分的左半边数组再一次切分
            mergeSort(a, start, mid);
            //每次切分的右半边数组再一次切分
            mergeSort(a, mid + 1, end);
            //在左右两边都切分为两个有序数组的时候进行归并
            merge1(a, start, mid, end);
        }
    }
}
